---
categories: Combinatorics
---

Let $G$ be a finite group that acts on a set $X$. For each $g$ in $G$
let $X^g$ denote the set of elements in $X$ that are fixed by $g$. Then
the number of orbits $$|X/G| = \frac{1}{|G|} \sum_{g\in G} |X^g|.$$


## Problems
- [Necklace of Beads](http://poj.org/problem?id=1286)
- [TheBeautifulBoard](https://community.topcoder.com/stat?c=problem_statement&pm=9975)
- [Magic Bracelet](http://poj.org/problem?id=2888)
- [Lucy and the Flowers](https://www.codechef.com/problems/DECORATE)
- [Sorting Machine](http://www.spoj.com/problems/SRTMACH/)
- [Pizza Toppings](https://projecteuler.net/problem=281)
- [Alphabet soup](https://archive.algo.is/icpc/swerc/2011/SWERC-set.pdf) [^2]
- [Drum Decorator](https://codingcompetitions.withgoogle.com/codejam/round/0000000000433651/000000000043373a) [^1]
- [Count the Necklaces](https://www.hackerrank.com/contests/infinitum12/challenges/count-the-necklaces)
- [Cube Coloring](https://csacademy.com/contest/beta-round-8/task/cube-coloring/)

## See also
- [Pólya enumeration theorem]()


## External links
- [Burnsides Lemma](https://www.hackerrank.com/topics/burnsides-lemma)
- [Burnside's lemma: orbit-counting theorem (cube and necklace colorings)](https://web.archive.org/web/20190308141747/http://2000clicks.com/mathhelp/CountingBurnsidesLemma.aspx)
- [Burnside's lemma](http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html)
- [Burnside's Lemma](https://imomath.com/index.cgi?page=BurnsidesLemma)

[^1]: <http://codeforces.com/blog/entry/18204?#comment-231223>
[^2]: <https://archive.algo.is/icpc/swerc/2011/SWERC-sols.pdf>